﻿#include <iostream>

#define MaxTreeSize 4
typedef char TElemType;
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;


void InitTree(BiTree &BT) {
    BT = NULL;
}


void CreateTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == '#')
        e = NULL;
    else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        BT->data = e;
        CreateTree(BT->lchild);
        CreateTree(BT->rchild);
    }
}

void Visit(BiTree BT) {
    std::cout << BT->data;
}

void PreOder(BiTree BT) {
    if (BT) {
        Visit(BT);
        PreOder(BT->lchild);
        PreOder(BT->rchild);
    }
}

/*
 * 已知二叉树以二叉链表存储，编写算法完成：对于树中每个元素值为x的结点，删除以它为根的子树，并释放相应的空间。
 * 操作步骤：删除值为x的结点，意味着应将其父结点的左（右）子女指针置空，用层次遍历易于找到某结点的父结点。
 */

void Del_x_BiTNode(BiTree &BT) {
    if (BT) {
        Del_x_BiTNode(BT->lchild);
        Del_x_BiTNode(BT->rchild);
        free(BT);
    }

}


// 在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树
void Search(BiTree &BT, TElemType x) {
    if (BT) {  // 若根结点值为x，则删除整棵树
        if(BT->data==x){
            Del_x_BiTNode(BT);
            exit(0);
        }
    }
    BiTree queue[MaxTreeSize];  // 存放二叉树结点指针的队列，容量足够大
    int front = 0, rear = 0;
    BiTNode *p;  // 遍历指针
    queue[rear++] = BT; //根结点入队
    while (front != rear) {  // 队列非空
        p = queue[front++];  // 队首元素出队
        if (p->lchild) {  // 若左子树非空
            if (p->lchild->data == x) {   // 左子树符合删除条件
                Del_x_BiTNode(p->lchild);
                p->lchild = NULL;
            } else
                queue[rear++] = p->lchild;   // 不符合删除条件，左子树入队
        }
        if (p->rchild) {  // 若右子树非空
            if (p->rchild->data == x) {   // 右子树符合删除条件
                Del_x_BiTNode(p->rchild);
                p->rchild = NULL;
            } else
                queue[rear++] = p->rchild;  // 不符合删除条件，右子树入队
        }
    }
}


int main() {
    BiTree BT;
    InitTree(BT);
    std::cout << "请按照先序序列输入树结点创建一棵二叉树（'#'表示空）：\n";
    CreateTree(BT);

    TElemType x;
    std::cout << "请输入要删除的元素值：";
    std::cin >> x;
    std::cout << "对于树中每个元素值为x的结点，删除以它为根的子树";
    Search(BT, x);
    std::cout << "删除后的二叉树的前序遍历序列为：";
    PreOder(BT);


    return 0;
}